\section{Comparer les deux versions du graphe de distribution}
\label{Graph_diff}

Le but de l'étude de ce problème et de la recherche d'une solution est d'avoir des paramètres d'entrée pour l'algorithme qui devra calculer les deux coûts et décider comment se passera la distribution. Pour ce faire, il va falloir isoler les ajouts effectués, c'est-à-dire isoler les noeuds (instructions ou variables) qui ont été ajoutés au programme. \\

La plus grande problématique dans cette comparaison est que les noeuds n'ont pas d'identifiant unique. En effet, leur label est une variable ou une instruction, mais deux noeuds peuvent avoir un label identique sans pour autant être les mêmes: deux instructions peuvent faire la même chose (incrémentation de la même variable, par exemple) mais elles se trouvent à deux endroits différents et ne sont donc pas les mêmes. De plus, il se peut qu'une instruction soit retirée et qu'une instruction identique soit ajoutée au programme (à un autre endroit). Dans ce cas là, il serait impossible de savoir qu'il y a eu une modification. Toutes ces complications sont dues à une et une seule cause: aucun noeud ne peut être identifié de manière unique. \\

Cette section s'organise en deux sous-sections: la première dans laquelle il est question de trouver un moyen d'identifier les noeuds de manière unique et la seconde dans laquelle la comparaison de deux versions d'un graphe est réalisée.\\

\subsection{Identification des noeuds de manières unique}
\label{unique-identification-node}

Afin d'identifier de manière unique chaque noeud, un bonne méthode serait d'ajouter de l'information à un noeud comme, par exemple, les liens qu'il possède avec les autres noeuds. Cette idée fonctionne pour les blocs atomiques (les \texttt{WHEN} et autres blocs appelés depuis un \texttt{WHEN}) mais pas pour les instructions isolées dans des blocs (typiquement des \texttt{SEQUENCE} ou \texttt{METHOD}) n'étant pas appelés depuis un autre bloc atomique. En effet, une instruction isolée n'est reliée, dans le graphe, qu'à la (ou les) variable(s) qu'elle utilise. Dès lors, il est impossible de différencier, même en ajoutant l'information des liens, deux instructions isolées qui font la même chose (incrémentation de la même variable, par exemple). \\ 

La question est de savoir si cette dernière situation est rare ou fréquente. Etant donné que les applications dont il est question ici sont des applications de contrôles, celles-ci ayant la particularité de devoir réagir à des évènements, il est aisé de se rendre compte que la majeure partie du code sera constitué de \texttt{WHEN} ou de \texttt{METHOD} appelés depuis des \texttt{WHEN}. Dès lors, il est possible de faire l'hypothèse que les instructions isolées ne seront pas nombreuses et que celles-ci seront d'office redistribuée, même si elles n'ont pas été modifiées. Ceci ne ralentirait que très peu la distribution (augmentation du coût de redistribution) puisque ces instructions isolées peuvent être de deux types: \\

\begin{itemize}
	\item Elles utilisent une (ou plusieurs) variable(s) sur laquelle (lesquelles) une contrainte est imposée. Dans ce cas, la distribution est immédiate: sur le site de la variable;
	\item Elles utilisent une (ou plusieurs) variable(s) sur laquelle (lesquelles) aucune contrainte n'est imposée. Dans ce cas, il faudra un peu plus examiner le code (ce qui prendra un peu plus de temps) afin de trouver la meilleure assignation. \\
\end{itemize}

Pour résumer, maintenant que le problème des instructions isolées est écarté, afin de pouvoir identifier uniquement chacun des noeuds (non isolés, bien entendu), il va falloir définir les noeuds comme suit: \\

Soit un noeud $n$ ayant un label $L$ et $k > 1$ liens vers les noeuds $n_1$, $n_2$, $...$, $n_k$, la définition de $n$ est:

\begin{align}
	\label{definition-node}
	n = \lbrace L, \lbrace n_1, n_2, ..., n_k \rbrace \rbrace
\end{align}

\noindent
Il faut maintenant s'assurer que cette définition d'un noeud est bien unique. \\

\begin{proposition}
	\label{proposition-unique-node}
	Soit deux noeuds $n_1$ et $n_2$ ayant le même label et se trouvant chacun dans un \texttt{WHEN}. Avec la définition~\ref{definition-node} des noeuds, il est possible de différencier $n_1$ et $n_2$, c'est-à-dire que $n_1 \neq n_2$.
\end{proposition}

\begin{proof}[Preuve par l'absurde]
	Soit $n_1$ et $n_2$, deux instruction identiques (c'est-à-dire, deux noeuds avec le même label $L$), utilisant une variable $v$ et situés respectivement dans les \texttt{WHEN} $W_1$ et $W_2$ avec comme condition respective $C_1$ et $C_2$, avec $C_1 \neq C_2$. Pour plus de facilité, faisons l'hypothèse que les instructions $n_1$ et $n_2$ sont les uniques instructions de leur \texttt{WHEN}. Montrons qu'il n'est pas possible de différencier $n_1$ et $n_2$.
	
	\begin{align*}
		n_1 = n_2 &\Leftrightarrow \lbrace L, \lbrace v, C_1 \rbrace \rbrace = \lbrace L, \lbrace v, C_2 \rbrace \rbrace \\
		&\Leftrightarrow L = L \wedge v = v \wedge C_1 = C_2
	\end{align*}
	
	Etant donné l'hypothèse de départ, $L = L$ et $v = v$ sont vrais, tandis que $C_1 = C_2$ contredit cette même hypothèse de départ. Ce qui prouve que les noeuds sont différentiables. CQFD.
\end{proof}

Nous sommes maintenant sûr de pouvoir différencier les noeuds dans des blocs atomiques. Illustrons ceci par un exemple d'un petit bout de code avec deux instructions identiques dont les définitions permettent de les différencier. Afin de mieux comprendre les définitions de ces deux noeuds, le graphe associé à ce bout de code est représenté en figure~\ref{example_compare_nodes}.

\begin{verbatim}
	1: WHEN a == 0 THEN
	2:   a := a + 1;
	3: END_WHEN
	4: 
	5: WHEN b == FALSE THEN
	6:   a := a + 1;
	7:   b := TRUE;
	8: END_WHEN
\end{verbatim}

\begin{figure}[htb]
	\label{example_compare_nodes}
	\begin{center}
		\includegraphics[scale=0.75]{Images/image_5_2.pdf}
		\caption{\textsl{Graphe} de l'exemple}
	\end{center}
\end{figure}

\noindent
Selon~(\ref{definition-node}), voici la définition des noeuds (2) et (6):

\begin{description}
	\item[\texttt{(2) a := a + 1}]$ = \lbrace($\texttt{a := a + 1}$),\; \lbrace($\texttt{a}$),\; ($\texttt{WHEN a == 0 THEN}$)\rbrace \rbrace$
	\item[\texttt{(6) a := a + 1}]$ = \lbrace($\texttt{a := a + 1}$),\; \lbrace($\texttt{a}$),\; ($\texttt{WHEN b == FALSE THEN}$),\; ($\texttt{b := TRUE}$)\rbrace \rbrace$
\end{description}

Maintenant que nous sommes capables d'identifier les instructions (dans les blocs atomiques) de manière unique et que nous avons décider de ne pas s'occuper des instructions isolées (ils seront considérés, comme dit plus haut, comme étant des ajouts), nous pouvons définir une façon de comparer deux version d'un bout de code, via le graphe.

\subsection{Comparaison de deux versions d'un graphe}
\label{section-compare-graph}

Le but de cette sous-section est de définir une méthode qui permettrait d'isoler les ajouts effectués à un programme en comparant l'ancienne et la nouvelle version du graphe associé au code de ce programme. Pour ce faire, nous avons défini une façon de rendre chaque noeud (ou plutôt les noeuds des blocs atomiques) uniquement identifiable afin de pouvoir comparer ces graphes. Voyons maintenant comment faire cette comparaison. \\

Trois ensembles de noeuds pourraient être identifiés après comparaison de deux versions d'un graphe: \\

\begin{itemize}
	\item Les noeuds inchangés
	\item Les noeuds ajoutés
	\item Les noeuds supprimés\\
\end{itemize}

En fait, il existe un quatrième ensemble, celui des noeuds modifiés mais, ici, un noeud $a$ modifié en $a'$ sera considéré comme une suppression de $a$ et un ajout de $a'$, pour plus de facilité. Le but de cette comparaison sera donc de reconstituer les trois ensembles définis ci-dessus. Pour ce faire, les graphes seront considérés en terme d'ensemble de noeuds~\footnote{Il n'est pas nécessaire de considérer l'ensemble des arcs, puisque la définition du noeud contient les liens de ce noeud vers ses voisins. Dès lors, il suffit de reconstituer le graphe à partir de ces informations.} et des opérations sur ces ensembles seront effectués. \\

Dans la suite, une série de notations seront utilisées: $G$ sera le graphe considéré qui aura $V_1$ et $V_2$, respectivement pour ancien et nouvel ensemble de noeud. L'ensemble des noeuds inchangés sera noté $V_i$, celui des noeuds ajoutés sera noté $V_a$ et, enfin, l'ensemble des noeuds supprimés sera noté $V_s$. Voyons maintenant comment identifier, dans l'ordre, $V_i$, $V_a$ et $V_s$. \\

\begin{description}
	\item[Les noeuds inchangés] Il est aisé de voir qu'isoler les noeuds inchangés entre deux ensembles revient à réaliser l'opération d'intersection entre ces deux ensembles: $V_i = V_1 \cap V_2$.
	\item[Les noeuds ajoutés] Pour construire cet ensemble, il va falloir utiliser l'ensemble $V_i$. En effet, les noeuds ajoutés sont les noeuds dans $V_2$ non repris dans $V_i$. Il s'agit donc d'une opération de différence ensembliste: $V_a = V_2 \setminus V_i$.
	\item[Les noeuds supprimés] Enfin, symétriquement à la construction de $V_a$, $V_s$ sera construit en utilisant $V_i$. En effet, les noeuds supprimés sont les noeuds de $V_1$ non reprise dans $V_i$. Là, encore, il s'agit d'une opération de différence ensembliste: $V_s = V_1 \setminus V_i$.\\
\end{description}

Nous sommes donc capables, à partir de deux versions d'un graphe, de construire les trois ensembles nécessaires à la redistribution. Avant de passer à la suite, voyons un peu la construction de ces trois ensembles en terme d'algorithmes. \\

Dans la librairie standard C++~\footnote{Et également dans la librairie Java et, probablement, dans les librairies d'autres langages.}, sont définis une multitude d'algorithmes pour les opérations ensemblistes dont, notamment, les opérations de différences et d'intersection (que l'on peut retrouver dans~\cite{BS}) qui sont utilisés ici. Comme les algorithmes ne viennent jamais sans leur complexité, voici donc les complexités des deux algorithmes: \\

\begin{description}
	\item[Complexité au pire cas de l'algorithme d'intersection ensembliste:~\cite{CppRefSI}] $2*(n+m)-1$, $n$ et $m$ étant les tailles des deux ensembles;
	\item[Complexité au pire cas de l'algorithme de différence ensembliste:~\cite{CppRefSD}] $2*(n+m)-1$, $n$ et $m$ étant les tailles des deux ensembles. \\
\end{description}

\noindent
Ce qui ramène la complexité de l'algorithme de comparaison de deux versions d'un graphe à : $3*\left[ 2*(n+m)-1 \right]$ \\

Avant de passer à la suite de la redistribution, illustrons la comparaison en reprenant l'exemple en fin de section~\ref{unique-identification-node} et en le modifiant. Imaginons que nous désirons rajouter l'instruction \texttt{b := FALSE} à la fin du premier \texttt{WHEN}, ainsi qu'ajouter un \texttt{WHEN}. Le code devient:

\begin{verbatim}
	01: WHEN a == 0 THEN
	02:   a := a + 1;
	03:   b := FALSE;
	04: END_WHEN
	05: 
	06: WHEN b == FALSE THEN
	07:   a := a + 1;
	08:   b := TRUE;
	09: END_WHEN
	10:
	11: WHEN a > 10 THEN
	12:   a := 0;
	13:   b := TRUE;
	14: END_WHEN
\end{verbatim}

\begin{figure}[htb]
	\begin{center}
		\includegraphics[scale=0.7]{Images/image_5_2_02.pdf}
		\caption{\textsl{Graphe} de l'exemple modifié}
		\label{modified-example}
	\end{center}
\end{figure}

La figure~\ref{modified-example} montre les trois noeuds ajoutés (le contour de ces noeuds sont en vert). Appliquons la méthode de comparaison expliquée ci-dessus à cet exemple. Tout d'abord, les deux ensembles des noeuds de l'ancienne et la nouvelle (les noeuds ajoutés sont coloré en vert, pour plus de lisibilité) version du graphe sont définis ci-dessous.  \\

\begin{align*}
	V_1 = \lbrace \; & \\
	\; & (WHEN \; a \; == \; 0 \; THEN), \; \lbrace (a \; := \; a + 1), (a) \rbrace ; \\
	\; & (a \; := \; a + 1), \; \lbrace (WHEN \; a \; == \; 0 \; THEN), (a) \rbrace ; \\
	\; & (WHEN \; b \; == \; FALSE \; THEN), \lbrace (a \; := \; a + 1), (b \; := \; TRUE), (b) \rbrace ; \\
	\; & (a \; := \; a + 1), \lbrace (WHEN \; b \; == \; FALSE \; THEN), (b \; := \; TRUE), (a) \rbrace ; \\
	\; & (b \; := \; TRUE), \lbrace (WHEN \; b \; == \; FALSE \; THEN), (a \; := \; a + 1), (b) \rbrace \\
	\rbrace \; &
\end{align*}
\begin{align*}
	V_2 = \lbrace \; & \\
	\; & (WHEN \; a \; == \; 0 \; THEN), \; \lbrace (a \; := \; a + 1), (a) \rbrace ; \\
	\; & (a \; := \; a + 1), \; \lbrace (WHEN \; a \; == \; 0 \; THEN), (a) \rbrace ; \\
	\; & (WHEN \; b \; == \; FALSE \; THEN), \lbrace (a \; := \; a + 1), (b \; := \; TRUE), (b) \rbrace ; \\
	\; & (a \; := \; a + 1), \lbrace (WHEN \; b \; == \; FALSE \; THEN), (b \; := \; TRUE), (a) \rbrace ; \\
	\; & (b \; := \; TRUE), \lbrace (WHEN \; b \; == \; FALSE \; THEN), (a \; := \; a + 1), (b) \rbrace ; \\
	\; & {\color{ForestGreen}(b \; := \; FALSE), \; \lbrace (a \; := \; a + 1), (WHEN \; a \; == 0 \; THEN), (b) \rbrace} ; \\
	\; & {\color{ForestGreen}(WHEN \; a > 10 \; THEN), \; \lbrace (a \; := \; 0), (b \; := \; TRUE), (a) \rbrace} ; \\
	\; & {\color{ForestGreen}(a \; := \; 0), \; \lbrace (WHEN \; a > 10 \; THEN), (b \; := \; TRUE), (a) \rbrace} ; \\
	\; & {\color{ForestGreen}(b \; := \; TRUE), \; \lbrace (WHEN \; a > 10 \; THEN), (a \; := \; 0), (b) \rbrace} ; \\
	\rbrace \; 
\end{align*}

Il faut maintenant calculer $V_i$ et $V_a$ ($V_s$ est délibérément omis puisqu'aucune suppression n'a été faite), et s'assurer que les noeuds contenus dans ces ensembles sont ceux voulus: \\

\begin{align*}
	V_i = & V_1 \cap V_2 \\
	\lbrace \; & \\
	\; & (WHEN \; a \; == \; 0 \; THEN), \; \lbrace (a \; := \; a + 1), (a) \rbrace, \\
	\; & (a \; := \; a + 1), \; \lbrace (WHEN \; a \; == \; 0 \; THEN), (a) \rbrace \\
	\; & (WHEN \; b \; == \; FALSE \; THEN), \lbrace (a \; := \; a + 1), (b \; := \; TRUE), (b) \rbrace ; \\
	\; & (a \; := \; a + 1), \lbrace (WHEN \; b \; == \; FALSE \; THEN), (b \; := \; TRUE), (a) \rbrace ; \\
	\; & (b \; := \; TRUE), \lbrace (WHEN \; b \; == \; FALSE \; THEN), (a \; := \; a + 1), (b) \rbrace \\
	\rbrace \; &
\end{align*}
\begin{align*}
	V_a = & V_2 \setminus V_i \\
	\lbrace \; & \\
	\; & (b \; := \; FALSE), \; \lbrace (a \; := \; a + 1), (WHEN \; a \; == 0 \; THEN), (b) \rbrace ; \\
	\; & (WHEN \; a > 10 \; THEN), \; \lbrace (a \; := \; 0), (b \; := \; TRUE), (a) \rbrace ; \\
	\; & (a \; := \; 0), \; \lbrace (WHEN \; a > 10 \; THEN), (b \; := \; TRUE), (a) \rbrace ; \\
	\; & (b \; := \; TRUE), \; \lbrace (WHEN \; a > 10 \; THEN), (a \; := \; 0), (b) \rbrace ; \\
	\rbrace \; &
\end{align*}

Il est aisé de se rendre compte que, étant donné qu'il n'y a pas eu d'ajout, $V_i$, l'ensemble des noeuds inchangés, est égal à $V_1$, l'ensemble des noeuds de l'ancienne version. Pour ce qui est de $V_a$, il n'est pas compliqué de s'apercevoir que $V_2 \setminus V_i$ ne laissera que ce qui est coloré en vert dans $V_2$, c'est-à-dire les noeuds ajoutés. Les ensembles $V_i$, $V_a$ et $V_s$ (qui est vide) ont dont correctement été créés par la méthode de comparaison décrite dans cette section. \\

Une chose reste à préciser: le cas des noeuds isolés. En effet, la technique qui vient d'être illustrée fonctionne pour les noeuds dans des blocs atomiques mais ce n'et pas le cas des noeuds isolés. La principale raison est que ces noeuds isolés n'ont que pour unique lien la variable qu'ils utilisent. Or, deux instructions qui sont identiques (et qui utilisent la même variable) ne peuvent donc pas être différenciées. Et, comme ces cas de noeuds isolés sont rares (le code d'une application de contrôle contient surtout des blocs atomiques comme des \texttt{WHEN}), ils seront directement considérés comme étant des ajouts. Ceci s'explique également par le fait que la suppression et l'ajout de deux instructions qui se ressemblent ne pourra pas être détectée. Pour réaliser ceci, il va falloir, avant de faire les opérations ensemblistes, retirer ces noeuds isolés de l'ensemble $V_1$. En effet, lors de l'opération $V_1 \cap V_2$, ces noeuds ne seront pas repris dans $V_i$ et, donc, seront considérés comme ajouts. \\

Ceci clôture cette section sur la comparaison de deux versions d'un graphe associé à un code de programme. Les trois ensembles construits, $V_i$, $V_a$ et $V_s$ seront utilisés dans la suite de la redistribution. 